// 提交链接 https://leetcode.cn/problems/kth-missing-positive-number/submissions/565390265/
// 1539. 第k个缺失的正整数
// 完成日期： 2024.9.17
// 二分搜索
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        if (arr[0] > k) return k;
        int head = 0, tail = arr.size() - 1;
        while (head < tail)
        {
            int mid = (head + tail ) / 2  +1;
            if (arr[mid] - mid - 1 < k) head = mid;
            else tail = mid - 1;
        }
        return arr[head] + (k - (arr[head] - head - 1));
    }
};